#leetcode题目82：删除排序链表中的重复元素II
#难度：中等




from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class LinkList:
    def __init__(self):
        self.head = None

    def initList(self, data):
        if not data:
            return None
        
        # 创建头结点
        self.head = ListNode(data[0])
        r = self.head
        p = self.head
        
        # 逐个为 data 内的数据创建结点,建立链表
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r

    def printlist(self, head):
        if head == None:
            return
        node = head
        while node != None:
            print(node.val, end=' ')
            node = node.next
        print()  # 换行

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        dump = ListNode(0,head)
        cur  = dump
        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                x=cur.next.val
                while cur.next and cur.next.val == x:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return dump.next


#测试数据
data=[1,2,3,3,4,4,5]
#预期输出：[1,2,5]
solution=Solution()
head=LinkList().initList(data)
LinkList().printlist(solution.deleteDuplicates(head))


data=[1,1,1,2,3]
#预期输出：[2,3]
solution=Solution()
head=LinkList().initList(data)
LinkList().printlist(solution.deleteDuplicates(head))